During the creation of a virtual environment, and as described in U.S. patent application Ser. No. 08/520,099 now U.S. Pat. No. 5,736,990 by John W. Barrus and Richard C. Waters filed on Aug. 28, 1995 and assigned to the assignee hereof, and incorporated herein by reference, virtual or simulated environments may be created through the utilization of so-called locales. Each of the locales defines a region of the virtual environment in terms of a perimeter and its own local origin. A locale is defined as a geometric area in which the distance between discrete representable positions at the limits of that area are small enough to be considered insignificant. Thus the locales have the characteristic that they are defined by a boundary and that they have their own individual origins such that all graphical objects within a locale are located with respect to the particular origin. This permits the creation of a virtual environment by a number of individual designers, each having independent control of the locales he is responsible for. Having created a virtual environment in this manner, it is possible to utilize the locales concept to manage control of the environment when the environment is exercised by multiple users.
A locale is a self contained subdivision of a part of a virtual environment each with its own model and each with its own boundary and its own origin. This permits graphical objects within a locale to be accurately located with respect to this local origin and also permits management of neighboring models merely through the specification of an agreed upon distance between the respective locale origins and locale orientations.
When a network is utilized, the data from each of the locales is multicast onto the network so that data relating to graphical objects in the locale as well as the background or terrain is available to every user. If there are many locales, a very large number of messages are sent over the network. This can tax the carrying capacity of the network, but long before the network becomes overloaded, the large number of messages can swamp the ability of any one user at a network node to receive and process them.
In order to solve this problem, each locale is assigned a separate multicast address so that individual nodes need not listen to every message, but rather only to the messages associated with the subset of locales that are relevant to the processing at the node. In particular, if the point of view of a node is in a given locale, then the node is configured so that it only receives messages relating to that one locale and its immediate neighbors with the node ignoring the messages from all other locales.
The importance of having a node ignore much of the data in a virtual environment is that it greatly reduces the computation required at any given node. However, it introduces a problem. The fact that information is being ignored means that there are some objects that a given node knows nothing about. In particular, it does not know what locales these objects are in. Therefore, it does not know what multicast address to listen to in order to find out about these objects. In short, if a node does not know about a given object, there is no way for it to ever find out anything about it. This means that as a practical matter, one cannot ignore anything unless some means is provided for finding the ignored objects again later.
The severity of the problem posed by large virtual environments from a computation and storage point of view can be seen by the following example. Assume that one wishes to simulate a building having 50 rooms, each corresponding to a different locale. Assume that on average each room, and therefore locale, contains 50 objects. Assume that graphical images are being generated at 30 frames per second. Assume that some of the objects are moving and require many messages per second to describe their frame-by-frame positions, while most objects are standing still and require only one message every few seconds to describe them. Finally, assume that this results in 1 message per second per object on average. This means there are 50 messages per second per room, and 2,500 messages per second for the building as a whole. If one was modeling a virtual city with 100 such buildings a total of 250,000 messages per second would be required.
Consider what the above example implies from the point of view of network bandwidth, processing power at a processing node, and memory requirements at a processing node. Assume that on average 100 bytes are required to represent a message, 0.0001 second is required to process a message, and 10,000 bytes are required to represent all the features of an object in memory. This implies that for a single room, 5000 bytes per second are transmitted, easily within the capabilities of almost any network, 0.005 seconds are required to process the messages, a very minor load on the processor, and 500,000 bytes of storage are required in the processing node, again a small load by today's standards. However, for the building as a whole, 250,000 bytes per second are transmitted, taxing but still within the capabilities of most current networks. Fully 0.25 seconds per second are required for processing messages, an unreasonable load given that the node as a great deal of other processing to do. Further, 25,000,000 bytes of storage are required for objects, beyond the capabilities of many of today's machines. Lastly, consider that for a virtual city of 100 such buildings, 25,000,000 bytes per second are transmitted, possible with high speed networks of various kinds. Also, 25 seconds per second are required to process messages, which makes real time performance impossible. Finally, 2,500,000,000 bytes of storage are required, which is equally impractical.
The key to avoiding the costs above is to realize that a person participating in a virtual meeting in a room does not need to know about anything except what is happening in that room and perhaps a few adjacent rooms. He certainly does not need to know anything about what is happening in rooms on other floors. This means that no matter how large the virtual building or city, the processing node being used by this person only needs to process a few hundred messages at most, if it ignores the messages from the rooms it does not care about, that is to say ignores the messages associated with rooms that do not neighbor the room the person is in. In order to do this in a multicast environment, one may merely exclude data having addresses relating to non-neighboring locales. By non-neighboring is meant non-contiguous.
The truncation of information described above allows the processing and memory requirements placed on the processing node to be small. However, it brings up a problem. Were one to try to locate the janitor, and assuming the janitor was in the basement and not near the room to be serviced, one could not provide a virtual rendition of the janitor since the address of the locale he is in is not known. A related problem is that it is even difficult to follow an object as it moves from one locale to another. If it moves slowly enough, one can relatively easily keep track of than object as it moves from one locale to a neighboring locale, however, it is possible that the object may be quickly jumped from one locale to a non-neighboring locale. In this case, one can loose track of the object. In both situations, what is necessary is a system for finding objects in non-neighboring locales, and to do so in such a manner that neither, network bandwidth, processing requirements, nor memory requirements are significantly increased.